<html>
<head><meta charset="utf-8"><title>eliminating side-effects of iterator adapters · t-libs · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/index.html">t-libs</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/eliminating.20side-effects.20of.20iterator.20adapters.html">eliminating side-effects of iterator adapters</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="241428786"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/eliminating%20side-effects%20of%20iterator%20adapters/near/241428786" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> The 8472 <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/eliminating.20side-effects.20of.20iterator.20adapters.html#241428786">(Jun 03 2021 at 17:56)</a>:</h4>
<p>Eliminating side-effects from various iterator adapters could have some benefits<br>
a) performance, the best case scenario would be turning some infinite iterations into constant time!<br>
b) simplification, especially around the unsafe code in <code>Zip</code><br>
c) turn some bugs into sanctioned behavior (at least one of them is my fault, I'm biased here <span aria-label="kiss with blush" class="emoji emoji-1f61a" role="img" title="kiss with blush">:kiss_with_blush:</span><span aria-label="musical notes" class="emoji emoji-1f3b6" role="img" title="musical notes">:musical_notes:</span>)</p>
<p>This could be introduced in a piecemeal fashion. Updating the documentation on the <code>iter</code> module to document that implementations <em>may</em> omit side-effects as long as they still produce the same final result. Then new methods could make use of it, e.g. the not yet stabilized <code>advance_by</code>.<br>
But updating <code>Zip</code> would be a breaking change and there are others too.</p>
<p>And there are obvious downsides. Some side-effects are non-obvious and usually not intentional and thus easy to eliminate but others may be more likely to break user code when they're using iterators over <code>&amp;mut</code> or closures that capture mutable state. Worst case would be that they do all their logic in an <code>inspect</code> closure and then call <code>count()</code> or something similar.</p>
<p>Should this go through an RFC? Would an incremental approach with crater runs along the way be fine? Is this even the right place or should I ask on IRLO?</p>



<a name="241430129"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/eliminating%20side-effects%20of%20iterator%20adapters/near/241430129" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nagisa <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/eliminating.20side-effects.20of.20iterator.20adapters.html#241430129">(Jun 03 2021 at 18:07)</a>:</h4>
<p>The existing methods likely won't be able to change here. But we could, I guess, add some new ones!</p>



<a name="241430292"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/eliminating%20side-effects%20of%20iterator%20adapters/near/241430292" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> simulacrum <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/eliminating.20side-effects.20of.20iterator.20adapters.html#241430292">(Jun 03 2021 at 18:09)</a>:</h4>
<p>Yeah, I don't think crater or rfcs are enough to consider things as side-effect free</p>



<a name="241432159"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/eliminating%20side-effects%20of%20iterator%20adapters/near/241432159" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> scottmcm <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/eliminating.20side-effects.20of.20iterator.20adapters.html#241432159">(Jun 03 2021 at 18:24)</a>:</h4>
<p>It feels to me like <code>map</code> taking <code>FnMut</code>, for example, is an implicit promise that the side effects are preserved and predictable.</p>
<p>A different version that only took <code>Fn</code>, though, would make skipping them seem reasonable to me, since while of course it's <em>possible</em> to use interior mutability to do things in that (well, or to just call functions with side effects), it feels way more sketchy to be relying upon it.</p>



<a name="241432197"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/eliminating%20side-effects%20of%20iterator%20adapters/near/241432197" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> scottmcm <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/eliminating.20side-effects.20of.20iterator.20adapters.html#241432197">(Jun 03 2021 at 18:24)</a>:</h4>
<p>(Even though <code>Map</code>'s side effects for double-ended iterators are weird.)</p>



<a name="241432450"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/eliminating%20side-effects%20of%20iterator%20adapters/near/241432450" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> cuviper <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/eliminating.20side-effects.20of.20iterator.20adapters.html#241432450">(Jun 03 2021 at 18:26)</a>:</h4>
<p>rayon's version of <code>Map</code> does use <code>Fn</code>, by necessity, but I wouldn't think it at all weird for someone to increment an atomic or something along the way</p>



<a name="241432452"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/eliminating%20side-effects%20of%20iterator%20adapters/near/241432452" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> The 8472 <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/eliminating.20side-effects.20of.20iterator.20adapters.html#241432452">(Jun 03 2021 at 18:26)</a>:</h4>
<p>That <em>might</em> be possible to distinugish via specialization, but even then we would still be ignoring &amp;mut refs passed to the closure as iterator item.</p>



<a name="241432967"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/eliminating%20side-effects%20of%20iterator%20adapters/near/241432967" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> The 8472 <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/eliminating.20side-effects.20of.20iterator.20adapters.html#241432967">(Jun 03 2021 at 18:30)</a>:</h4>
<p>But ok, let's say we don't break existing methods, just remove buggy optimizations instead and move them to the new methods, what would the process then be? This would need duplication of many existing methods such as <code>inspect</code>, <code>filter</code>, <code>map</code>, <code>take</code>, <code>cloned</code>, <code>zip</code> and variants thereof.</p>



<a name="241433280"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/eliminating%20side-effects%20of%20iterator%20adapters/near/241433280" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> The 8472 <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/eliminating.20side-effects.20of.20iterator.20adapters.html#241433280">(Jun 03 2021 at 18:33)</a>:</h4>
<p>Seems like a fairly big change if it were done that way.</p>



<a name="241434502"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/eliminating%20side-effects%20of%20iterator%20adapters/near/241434502" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> scottmcm <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/eliminating.20side-effects.20of.20iterator.20adapters.html#241434502">(Jun 03 2021 at 18:42)</a>:</h4>
<p>I guess it'd need more info about how often the optimizations it could do happen to apply in "real" code.  Though that's admittedly super-hard to measure.</p>



<a name="241436500"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/eliminating%20side-effects%20of%20iterator%20adapters/near/241436500" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nagisa <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/eliminating.20side-effects.20of.20iterator.20adapters.html#241436500">(Jun 03 2021 at 18:57)</a>:</h4>
<p>We had written a fair number of specializations over time that were later either removed or just not accepted because they would fail to consider side-effects.</p>



<a name="241436617"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/eliminating%20side-effects%20of%20iterator%20adapters/near/241436617" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> The 8472 <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/eliminating.20side-effects.20of.20iterator.20adapters.html#241436617">(Jun 03 2021 at 18:58)</a>:</h4>
<p>The most obvious cases would be <code>iter.map().skip()</code> behaving the same as <code>iter.skip().map()</code> and <code>iter.take().map().next_back()</code> not evaluating the tail at all. Of course there may be some additional adapters between the relevant ones and it would still optimize.</p>
<p>For Zip it would be about<br>
A) not equalizing the iterator length during the first backwards iteration step (similar to the take + next_back case)<br>
B) not evaluating the remainder at when next() is called after  of forwards iteration returned <code>None</code> for the first time. For this case it could make sense to have a new method, that was proposed in <a href="https://github.com/rust-lang/rust/issues/85342">#85342</a><br>
Both already are broken in some cases and at least B) could arguably be justified with existing code, i.e. iteration via counted loops instead of waiting for <code>next().is_none()</code>.</p>
<p>But for other existing adapters like map/take etc. I'm it doesn't feel like it would be worth it to add new ones.</p>



<a name="241436623"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/eliminating%20side-effects%20of%20iterator%20adapters/near/241436623" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nagisa <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/eliminating.20side-effects.20of.20iterator.20adapters.html#241436623">(Jun 03 2021 at 18:58)</a>:</h4>
<p>A lot of them would provide significant-seeming benefits for comparatively common-looking iterator chains.</p>



<a name="241436672"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/eliminating%20side-effects%20of%20iterator%20adapters/near/241436672" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nagisa <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/eliminating.20side-effects.20of.20iterator.20adapters.html#241436672">(Jun 03 2021 at 18:58)</a>:</h4>
<p>.count() being able to just return the length for many iterators comes to mind.</p>



<a name="241436706"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/eliminating%20side-effects%20of%20iterator%20adapters/near/241436706" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> The 8472 <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/eliminating.20side-effects.20of.20iterator.20adapters.html#241436706">(Jun 03 2021 at 18:59)</a>:</h4>
<p>Yeah, that's another good one.</p>



<a name="241436891"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/eliminating%20side-effects%20of%20iterator%20adapters/near/241436891" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> The 8472 <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/eliminating.20side-effects.20of.20iterator.20adapters.html#241436891">(Jun 03 2021 at 19:00)</a>:</h4>
<p>We could let users opt into such optimizations but that may be unergonomic if they don't control the iterator source and it'll be hard to tell when it's beneficial etc. etc.</p>



<a name="241437059"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/eliminating%20side-effects%20of%20iterator%20adapters/near/241437059" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> oli <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/eliminating.20side-effects.20of.20iterator.20adapters.html#241437059">(Jun 03 2021 at 19:01)</a>:</h4>
<p>maybe we can write MIR opts that know about iterator adapters and will reshuffle them if provably side-effect-free?</p>



<a name="241437142"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/eliminating%20side-effects%20of%20iterator%20adapters/near/241437142" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> oli <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/eliminating.20side-effects.20of.20iterator.20adapters.html#241437142">(Jun 03 2021 at 19:02)</a>:</h4>
<p>most method chains on iterators look quite simple in MIR</p>



<a name="241437204"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/eliminating%20side-effects%20of%20iterator%20adapters/near/241437204" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> oli <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/eliminating.20side-effects.20of.20iterator.20adapters.html#241437204">(Jun 03 2021 at 19:02)</a>:</h4>
<p>and we can be arbitrarily pessimistic in the "no-side-effect" checks</p>



<a name="241437283"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/eliminating%20side-effects%20of%20iterator%20adapters/near/241437283" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> The 8472 <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/eliminating.20side-effects.20of.20iterator.20adapters.html#241437283">(Jun 03 2021 at 19:03)</a>:</h4>
<p>reshuffling would work for the map + skip case, but not for take + next_back</p>



<a name="241437546"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/eliminating%20side-effects%20of%20iterator%20adapters/near/241437546" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nagisa <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/eliminating.20side-effects.20of.20iterator.20adapters.html#241437546">(Jun 03 2021 at 19:05)</a>:</h4>
<p>After some inlining and whatnot LLVM should be able to see what things are side-effect free quite often and remove them too.</p>



<a name="241437795"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/eliminating%20side-effects%20of%20iterator%20adapters/near/241437795" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> The 8472 <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/eliminating.20side-effects.20of.20iterator.20adapters.html#241437795">(Jun 03 2021 at 19:07)</a>:</h4>
<p>LLVM's concept of side-effect may not be the programmer's. e.g. an <code>.inspect(|x| println!("{}", x))</code> would be an eliminatable side-effect for my purposes but certainly not for llvm.</p>



<a name="241438040"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/eliminating%20side-effects%20of%20iterator%20adapters/near/241438040" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nagisa <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/eliminating.20side-effects.20of.20iterator.20adapters.html#241438040">(Jun 03 2021 at 19:09)</a>:</h4>
<p>Yeah. For these MIR optimizations won't really help either. Because it needs some framework of proving side-effect-free-ness, and if you asked MIR if print is, then it definitely is a side-effect.</p>



<a name="241438956"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/eliminating%20side-effects%20of%20iterator%20adapters/near/241438956" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> The 8472 <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/eliminating.20side-effects.20of.20iterator.20adapters.html#241438956">(Jun 03 2021 at 19:16)</a>:</h4>
<p>I guess I'll start smaller then. Revert current breakage. A documentation update that adapters <em>may</em> elide side-effects, which will help future or 3rd-party adapters. Then <code>zip_exact</code>. And maybe experiment with specializing on Fn vs. FnMut and see if that works. The team can still tell me to write an RFC at any point <span aria-label="shrug" class="emoji emoji-1f937" role="img" title="shrug">:shrug:</span>‍♂️</p>



<a name="245718334"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/eliminating%20side-effects%20of%20iterator%20adapters/near/245718334" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> The 8472 <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/eliminating.20side-effects.20of.20iterator.20adapters.html#245718334">(Jul 12 2021 at 17:22)</a>:</h4>
<p>Another uncooked idea: What if we add a new generic argument to the Adapters that take closures? E.g. <code>Map&lt;I, F, Effects=Keep&gt;</code>. Could an edition change then somehow flip the default to <code>Map&lt;I, F, Effects=Skippable&gt;</code> by changing the return types on the <code>Iterator</code> methods?</p>



<a name="245719153"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/eliminating%20side-effects%20of%20iterator%20adapters/near/245719153" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> The 8472 <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/eliminating.20side-effects.20of.20iterator.20adapters.html#245719153">(Jul 12 2021 at 17:28)</a>:</h4>
<p>By "changing" I mean that different editions see different methods under the same name.</p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>